﻿using System;
using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_122 : BaseProblem
    {
        public override object GetResult()
        {
            const int max = 200;

            long res = 0;
            var dct = new Dictionary<long, long>();
            FormeRec(ref dct,  new List<long>(){1, 2}, 3*max/2);
            for (var i = 1; i <= max; i++ )
            {
                if (dct.ContainsKey(i))
                    res += dct[i];
            }
            return res+1;
        }

        private static void FormeRec(ref Dictionary<long, long> dct, IList<long> vals, long max)
        {
            var prev = vals[vals.Count - 1];
            for (var i = vals.Count - 1; i >= 0; i-- )
            {
                var l = vals[i];
                var qq = l + prev;
                if (qq > max) break;
                var tmp = new List<long>(vals) { qq };
                if (!dct.ContainsKey(qq))
                {
                    dct.Add(l + prev, vals.Count);
                    if (dct.Count >= max - 1) return;
                    FormeRec(ref dct, tmp, max);
                }
                else
                {
                    if (vals.Count <= dct[l + prev])
                    {
                        dct[l + prev] = vals.Count;
                        FormeRec(ref dct, tmp, max);
                    }
                }
                
            }
        }

        public override string Problem
        {
            get
            {
                return @"The most naive way of computing n15 requires fourteen multiplications:

n  n  ...  n = n15
But using a 'binary' method you can compute it in six multiplications:

n  n = n2
n2  n2 = n4
n4  n4 = n8
n8  n4 = n12
n12  n2 = n14
n14  n = n15
However it is yet possible to compute it in only five multiplications:

n  n = n2
n2  n = n3
n3  n3 = n6
n6  n6 = n12
n12  n3 = n15
We shall define m(k) to be the minimum number of multiplications to compute nk; for example m(15) = 5.

For 1  k  200, find  m(k).";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 1582;
            }
        }

    }
}
